package leetcode_900;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import helpclass.TreeNode;

/**
 *@author 周杨
 *AllNodesDistanceKInBinaryTree_863 给定一颗二叉树 返回某个节点距离K 的所有节点
 *describe:重构该二叉树 用广度优先遍历 AC 25%
 *2018年11月5日 下午12:47:34
 */
public class AllNodesDistanceKInBinaryTree_863 {
	Map<Integer,List<Integer>> map;
	public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
		this.map=new HashMap<Integer,List<Integer>>();
		help(root);//已经确保了树不为空
		Queue<Integer> queue=new LinkedList<Integer>();
		queue.offer(target.val);
		List<Integer> res=new ArrayList<Integer>();
		Set<Integer>visited=new HashSet<Integer>();
		while(K>0&&!queue.isEmpty()) {
			--K;
			int size=queue.size();
			while(size>0) {
				--size;
				int now=queue.poll();
				visited.add(now);
				List<Integer> list=map.get(now);
				if(list!=null)
					for(int i:map.get(now)) {
						if(!visited.contains(i))
							queue.offer(i);
					}
			}
		}
		while(!queue.isEmpty())
			res.add(queue.poll());
		return res;	
    }
	
	public void help(TreeNode root) {
		List<Integer> rootList=this.map.get(root.val);
		if(root.left!=null) {//为左子树添加入map
			if(rootList==null) {
				rootList=new ArrayList<Integer>();
			}
			rootList.add(root.left.val);
			List<Integer> leftList=this.map.get(root.left.val);
			if(leftList==null) {
				leftList=new ArrayList<Integer>();
			}
			leftList.add(root.val);
			this.map.put(root.val, rootList);
			this.map.put(root.left.val, leftList);
			help(root.left);//遍历左子树
		}
		if(root.right!=null) {	
			if(rootList==null) {
				rootList=new ArrayList<Integer>();
			}
			rootList.add(root.right.val);
			List<Integer> rightList=this.map.get(root.right.val);
			if(rightList==null) {
				rightList=new ArrayList<Integer>();
			}
			rightList.add(root.val);
			this.map.put(root.val, rootList);
			this.map.put(root.right.val, rightList);
			help(root.right);//遍历右子树
		}
	}
}
